#include <iostream>
#include <functional>
#include <algorithm>
#include <iterator>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cstdio>

using namespace std;

class mi_rand
{
    public:
        mi_rand (int start_pos, int end_pos) : a(start_pos), b(end_pos) 
        {
            if (a > b) swap(a,b);
            srand ((unsigned) time(NULL));
        }

        unsigned operator () () 
        {
            return rand() % (b-a+1) + a;
        }

    private:
        int a, b;
};

void bucket_sort (int *org, const int size, int digit = 10);

int main()
{
    const int SIZE = 10;
    int array[SIZE];
    generate_n (array, SIZE, mi_rand (1, 10));
    
    copy (array, array + SIZE, 
          ostream_iterator<int> (cout, " "));
    cout << endl;

    bucket_sort (array, SIZE);

    copy (array, array + SIZE, 
          ostream_iterator<int> (cout, " "));
    cout << endl;

    return 0;
}

void bucket_sort (int *org, const int size, int digit)
{
    int bucket[10][size];
    fill_n ((int*)bucket, 10*size, 0);
    int* nums[size];
    int *foo = org;

    for (int i = 0; i < size; ++i)
        nums[i] = bucket[i];

    for (int i = 0; i < size; ++i)
    {
        if (org[i] < digit/10)
            *(nums[0]++) = org[i];
        else
            *(nums[org[i] % digit]++) = org[i];
    }

    for (int i = 0; i < 10; ++i)
    {
        cout << i << ": ";
        for (int* it = bucket[i]; it != nums[i]; ++it)
            cout << " " << *it << " ";
        cout << endl;
    }

    cout << endl;

    bool modified = false;

    for (int i = 0; i < 10; ++i)
        for (int* it = bucket[i]; it != nums[i]; ++it)
        {
            if (*it != *org) 
            {
                *(org++) = *it;
                modified = true;
            }
        }

    if (!modified) return;

    copy (foo, foo + size, 
          ostream_iterator<int> (cout, " "));
    cout << endl;

    bucket_sort (foo, size, digit*10);
    
}
